This present invention relates generally to an implementation of a fast fourier transform operation in a microprocessor system, and more particularly to a system and method for performing a fast fourier transform using a matrix-vector multiply instruction.
A fourier transform is a mathematical tool that is used to analyze continuous waveforms for repeating patterns. In particular, a fourier transform is based on the analysis of waveforms by breaking up the waveform into sinusoid functions. Sinusoid functions have a xe2x80x9cwavyxe2x80x9d pattern that repeats at a given frequency.
In digital systems, digital waveforms are no longer continuous but are represented by a set of samples or points. A technique called a fast fourier transform (FFT) is used to analyze the digital waveforms for repeating patterns. The FFT is applied to the input samples or points, referred to as xi and generates a set of output points, referred to as Xi. The FFT requires a certain number of calculations and uses a large amount of processor time. In a radix-2 FFT, the total number of complex multiplications and additions is N log2N, where N is the number of samples or points in the waveform. For example, an analysis of a 1,024 point waveform uses about 10,000 complex additions and multiplications. Therefore a method and system that reduces the amount of processor and computation time to perform the FFT operation is desirable.
It is an object of the present invention to provide an improved apparatus for and method of performing a fast fourier transform that reduces the computation time.
It is a further object of the invention to provide an improved method and apparatus for performing the fast fourier transform using a matrix vector multiply instruction.
It is a related object of the invention to provide a new method and apparatus for performing an inverse discrete cosine transform operation that reduces computation time using the matrix vector multiply instruction.
These and other objectives and advantages of the present invention are achieved by utilizing a matrix vector multiply instruction referred to as an FTRV instruction in a processor to perform the FFT operation. For the FFT operation, the input data and coefficients of the FFT are rearranged and stored in a vector register and matrix register, respectively. The FTRV instruction is then used to perform a butterfly operation of the FFT.
More particularly, a processor executes a butterfly operation for a fast fourier transform operation. In the butterfly operation, a first set of inputs are defined as r1+j i1 and r2+j i2, and a twiddle factor, called Wn, is defined as Wn=e xe2x88x92j2xcfx80/N=cos(2xcfx80/N)xe2x88x92j sin(2xcfx80/N)=a+jb. A first set of registers store r1, i1, r2 and i2; and matrix registers store the twiddle factor. A matrix vector multiply operation is executed between the matrix registers and the first set of registers.
Other features and advantages of the present invention would become apparent to a person of skill in the art who studies the present invention disclosure. Therefore, a more detailed description of a preferred embodiment of the invention is given with respect to the following drawings.